The present invention relates generally to communication systems, and more particularly to allocating excess bandwidth in a differentiated services communication network.
In today""s information age, various networking devices, such as computers and computer peripherals, are frequently interconnected over a communication network. The networking devices include various networking applications that communicate over the communication network using a networking protocol. The communication network includes various networking nodes that route information between the networking devices based upon the networking protocol.
One common networking protocol is the Internet Protocol (IP). IP provides for connectionless communication between networking devices. Specifically, each networking device is associated with an IP address. Each protocol message sent from a source networking device to a destination networking device includes a source IP address associated with the source networking device and a destination IP address associated with the destination networking device. The networking nodes route each protocol message based upon at least the destination IP address.
In order to operate properly, some networking applications require the communication network to guarantee a certain quality of service (QoS) for the networking application. For example, the networking application may require a minimum amount of bandwidth, a maximum amount of end-to-end delay, a maximum amount of inter-message delay (jitter), or other services.
The basic IP architecture does not provide for such QoS guarantees. However, an architecture for Differentiated Services (Diffserv) has been defined within the Internet to Engineering Task Force (IETF) through a Request for Comments (RFC) to address QoS issues in IP networks. Diffserv is described in Blake, S. et al., xe2x80x9cAn Architecture for Differentiated Servicesxe2x80x9d, RFC 2475, December 1998, which is hereby incorporated herein by reference in its entirety.
The Diffserv architecture has recently become the preferred method to address QoS issues in IP networks. Diffserv utilizes a packet marking based approach to IP-QoS. This packet marking based approach to IP-QoS is attractive due to its simplicity and ability to scale. An end-to-end differentiated service is obtained by concatenation of per-domain services and Service Level Agreements (SLAs) between adjoining domains along the path that the traffic crosses in going from source to destination. Per domain services are realized by traffic conditioning at the edge and simple differentiated forwarding mechanisms at the core of the network. Two forwarding mechanisms recently standardized by the IETF are the Expedited Forwarding (EF) and Assured Forwarding (AF) Per Hop Behaviors (PHB). The EF PHB is described in Jacobson V, Nichols K, Poduri K, xe2x80x9cAn Expedited Forwarding PHBxe2x80x9d, RFC 2598, June 1999, which is hereby incorporated herein by reference in its entirety. The AF PHB is described in Heinanen J., Baker F., Weiss W., and Wroclawski J., xe2x80x9cAssured Forwarding PHB Groupxe2x80x9d, RFC 2597, June 1999, which is hereby incorporated herein by reference in its entirety.
The basis of the AF PHB is differentiated dropping of packets during congestion at the router. The differentiated dropping is achieved via Random Early Detection (RED)-like Active Queue Management (AQM) techniques. RED is described in Floyd, S., and Jacobson, V., xe2x80x9cRandom Early Detection gateways for Congestion Avoidancexe2x80x9d, IEEE/ACM Transactions on Networking, V. 1 N.4, August 1993, p. 397-413, which is hereby incorporated herein by reference in its entirety.
The AF PHB RFC specifies four classes and three levels of drop precedence per class. AF is an extension of the RIO scheme, which uses a single FIFO queue and two levels of drop precedence. RIO is described in Clark D. and Fang W., xe2x80x9cExplicit Allocation of Best Effort Packet Delivery Servicexe2x80x9d, IEEE/ACM Transactions on Networking, V.6 N. 4, August, 1998, which is hereby incorporated herein by reference in its entirety.
To build an end-to-end service with AF, subscribed traffic profiles for customers are maintained at the traffic conditioning nodes at the edge of the network. The aggregated traffic is monitored and packets are marked at the traffic conditioner. When the measured traffic exceeds the committed target rate, the packets are marked with higher drop precedence (DP1); otherwise packets are marked with lower drop precedence (DP0). If the measured traffic exceeds the peak target rate, the packets are marked with highest drop precedence (DP2). At the core of the network, at the time of congestion, the packets with DP1 marking have higher probability of being dropped than packets with DP0 marking. Similarly, packets with DP2 marking have higher probability of being dropped than packets with DP0 and DP1 marking. The different drop probabilities are achieved by maintaining three different sets of RED parametersxe2x80x94one for each of the drop precedence markings.
Recent studies of RIO-based schemes (see, for example, Ibanez J, Nichols K., xe2x80x9cPreliminary Simulation Evaluation of an Assured Servicexe2x80x9d, Internet Draft, draft-ibanez-diffserv-assured-eval-00.txt greater than , August 1998 or Seddigh, N., Nandy, B., Pieda, P, xe2x80x9cBandwidth Assurance Issues for TCP flows in a Differentiated Services Networkxe2x80x9d, In Proceedings of Globecom""99, Rio De Janeiro, December 1999, both of which are hereby incorporated herein by reference in their entireties) showed that in an over-provisioned (under-subscribed) network, target rates for all customers are mostly achieved. However, excess bandwidth may be unfairly divided amongst the equal-paying customers. This unfairness is caused by at least 5 different factors: Round Trip Time (RTT), packet size, size of target rate, number of microflows sharing target aggregate, and presence of non-responsive flows.
The studies on size of target rate indicate that excess bandwidth is not distributed in proportion to the target rate but rather is distributed almost evenly amongst the subscribed target aggregates. Thus, if 2 customers subscribed to a service with one customer paying for 1 Mbps and the other for 4 Mbps in a 10 Mbps capacity network, the first customer would get a total of 3.5 Mbps and the second customer would get 6.5 Mbps. Thus, even though the second customer subscribed to four times the rate of the first customer (and presumably paid closer to four times the amount), he/she is not even getting twice as much bandwidth as the first customer. The decision of how to distribute the excess bandwidth is really a business choice that should be made by the service provider. However, it would be useful if the provider had the technical capability to provide either proportional or even-distribution of the excess bandwidth should they desire. The present invention provides a mechanism for proportional distribution of the excess bandwidth.
In accordance with one aspect of the invention, a traffic conditioning method assigns a drop precedence value to each of a plurality of packets associated with a traffic stream having a target rate and a measured rate greater than the target rate such that, of all packets assigned either a first drop precedence value or a second drop precedence value higher than the first drop precedence value, substantially (1xe2x88x92q) of the packets are assigned the first drop precedence value and substantially (q) of the packets are assigned the second drop precedence value, where q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream.
In accordance with another aspect of the invention, a traffic conditioning method assigns a drop precedence value to a packet associated with a traffic stream having a target rate and a measured rate greater than the target rate by assigning a first drop precedence value to the packet with a probability (1xe2x88x92q) and assigning a second drop precedence value higher than the first drop precedence value to the packet with a probability (q), where q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream.
In accordance with yet another aspect of the invention, a traffic conditioning method assigns a drop precedence value to a packet associated with a traffic stream having a target rate and a measured rate by assigning a first drop precedence value to the packet with a probability (1xe2x88x92p), if the measured rate is greater than the target rate; assigning a second drop precedence value higher than the first drop precedence value to the packet with a probability (1xe2x88x92q), if the measured rate is greater than the target rate and the packet is not assigned the first drop precedence value with the probability (1xe2x88x92p); and assigning a third drop precedence value higher than the second drop precedence value to the packet, if the measured rate is greater than the target rate and the packet is assigned neither the first drop precedence value with the probability (1xe2x88x92p) nor the second drop precedence value with the probability (1xe2x88x92q) (i.e., the third drop precedence value is assigned with probability q), wherein p is equal to the ratio of the measured rate minus the target rate to the measured rate, and wherein q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream. The traffic conditioning method assigns the first drop precedence value to the packet, if the measured rate is less than or equal to the target rate.
In accordance with still another aspect of the invention, a device includes a target aware traffic conditioner for assigning a drop precedence value to a packet that is associated with a traffic stream having a target rate and a measured rate. The target aware traffic conditioner includes a packet marker for assigning a first drop precedence value to the packet with a probability (1xe2x88x92p), if the measured rate is greater than the target rate; assign a second drop precedence value higher than the first drop precedence value to the packet with probability a (1xe2x88x92q), if the measured rate is greater than the target rate and the packet is not assigned the first drop precedence value with the probability (1xe2x88x92p); and assign a third drop precedence value higher than the second drop precedence value to the packet, if the measured rate is greater than the target rate and the packet is assigned neither the first drop precedence value with probability the (1xe2x88x92p) nor the second drop precedence value with the probability (1xe2x88x92q) (i.e., the third drop precedence value is assigned with probability q), wherein p is equal to the ratio of the measured rate minus the target rate to the measured rate, and wherein q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream. The packet marker assigns the first drop precedence value to the packet, if the measured rate is less than or equal to the target rate. The target aware traffic conditioner also includes rate measurement logic for determining the measured rate for the traffic stream based upon packets received for the traffic stream and for providing the measured rate to the packet marker. The target aware traffic conditioner also includes a target rate storage for storing at least a minimum target rate for a plurality of traffic streams and the target rate for the traffic stream. The target aware traffic conditioner also includes a pseudo-random number generator operably coupled to provide random values to the packet marker. The packet marker assigns the first drop precedence value to the packet with the probability (1xe2x88x92p) by selecting a first random number from zero to one using the pseudo-random number generator and assigning the first drop precedence value to the packet if the first random number is less than the value (1xe2x88x92p). The packet marker assigns the second drop precedence value to the packet with probability a (1xe2x88x92q) by selecting a second random number from zero to one using the pseudo-random number generator and assigning the second drop precedence value to the packet if the second random number is less than the value (1xe2x88x92q). The packet marker assigns the third drop precedence value to the packet if the second random number is greater than or equal to the value (1xe2x88x92q).
In accordance with still another aspect of the invention, a program product includes a target aware traffic conditioner for assigning a drop precedence value to a packet that is associated with a traffic stream having a target rate and a measured rate. The target aware traffic conditioner includes a packet marker for assigning a first drop precedence value to the packet with a probability (1xe2x88x92p), if the measured rate is greater than the target rate; assign a second drop precedence value higher than the first drop precedence value to the packet with probability a (1xe2x88x92q), if the measured rate is greater than the target rate and the packet is not assigned the first drop precedence value with the probability (1xe2x88x92p); and assign a third drop precedence value higher than the second drop precedence value to the packet, if the measured rate is greater than the target rate and the packet is assigned neither the first drop precedence value with probability the (1xe2x88x92p) nor the second drop precedence value with the probability (1xe2x88x92q) (i.e., the third drop precedence value is assigned with probability q), wherein p is equal to the ratio of the measured rate minus the target rate to the measured rate, and wherein q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream. The packet marker assigns the first drop precedence value to the packet, if the measured rate is less than or equal to the target rate. The target aware traffic conditioner also includes rate measurement logic for determining the measured rate for the traffic stream based upon packets received for the traffic stream and for providing the measured rate to the packet marker. The packet marker obtains the minimum target rate for a plurality of traffic streams and the target rate for the traffic stream from a target rate storage. The packet marker assigns the first drop precedence value to the packet with the probability (1xe2x88x92p) by selecting a first random number from zero to one and assigning the first drop precedence value to the packet if the first random number is less than the value (1xe2x88x92p). The packet marker assigns the second drop precedence value to the packet with probability a (1xe2x88x92q) by selecting a second random number from zero to one and assigning the second drop precedence value to the packet if the second random number is less than the value (1xe2x88x92q). The packet marker assigns the third drop precedence value to the packet if the second random number is greater than or equal to the value (1xe2x88x92q).
In accordance with still another aspect of the invention, a communication system includes a plurality of traffic streams supported by at least one edge node and a core node. A traffic conditioning edge node supporting a traffic stream having a target rate and a measured rate greater than the target rate assigns a drop precedence value to each of a plurality of packets associated with the traffic stream such that, of all packets assigned either the first drop precedence value or the second drop precedence value, substantially (1xe2x88x92q) of the packets are assigned the first drop precedence value and substantially (q) of the packets are assigned the second drop precedence value, wherein q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream. The core node selectively drops packets based upon at least the drop precedence value assigned to each of the plurality of packets.
In various embodiments of the invention, the target aware traffic conditioner is used for supporting differentiated services using three drop precedence values per assured forwarding class for indicating a lowest drop precedence level, an intermediate drop precedence level, and a highest drop precedence level. When the measured rate for a traffic stream is less than or equal to the target rate for the traffic stream, the target aware traffic conditioner typically assigns all packets the lowest drop precedence level. When the measured rate for the traffic stream is greater than the target rate for the traffic stream, the target aware traffic conditioner may assign the lowest drop precedence level to a certain percentage of packet, but distributes the remaining packets between the intermediate drop precedence level and the highest drop precedence level such that a packet is assigned the intermediate drop precedence level with probability (1xe2x88x92q) and is assigned the highest drop precedence level with probability (q), wherein q is equal to the ratio of a minimum target rate from among a plurality of traffic streams to the target rate of the traffic stream.